package io.github.hadyang.leetcode.offer;

import java.util.ArrayList;
import org.junit.Test;

/** @author haoyang.shi */
public class GetUglyNumber {

  @Test
  public void test() {
    //        System.out.println(GetUglyNumber_Solution(1));
    //        System.out.println(GetUglyNumber_Solution(2));
    //        System.out.println(GetUglyNumber_Solution(3));
    System.out.println(GetUglyNumber_Solution(10));
  }

  public int GetUglyNumber_Solution(int index) {
    if (index == 0) {
      return 0;
    }

    if (index == 1) {
      return 1;
    }

    ArrayList<Integer> list = new ArrayList<>(index);
    list.add(1);

    int preIndex2 = 0;
    int preIndex3 = 0;
    int preIndex5 = 0;
    for (int i = 0; i < index; i++) {
      int next2 = list.get(preIndex2) * 2;
      int next3 = list.get(preIndex3) * 3;
      int next5 = list.get(preIndex5) * 5;

      int nextV = Math.min(Math.min(next2, next3), next5);
      list.add(nextV);

      while (preIndex2 < list.size() - 1 && list.get(preIndex2) * 2 <= nextV) preIndex2++;
      while (preIndex3 < list.size() - 1 && list.get(preIndex3) * 3 <= nextV) preIndex3++;
      while (preIndex5 < list.size() - 1 && list.get(preIndex5) * 5 <= nextV) preIndex5++;
    }

    return list.get(index - 1);
  }
}
